1

On the complexity of graph reconstruction

Year:
1994
Language:
english
File:
PDF, 942 KB
english, 1994
2

Using complexity to protect elections

Year:
2010
Language:
english
File:
PDF, 1.02 MB
english, 2010
3

Anyone but him: The complexity of precluding an alternative

Year:
2007
Language:
english
File:
PDF, 291 KB
english, 2007
8

Universally Serializable Computation

Year:
1997
Language:
english
File:
PDF, 371 KB
english, 1997
10

Reducing the Number of Solutions of NP Functions

Year:
2002
Language:
english
File:
PDF, 178 KB
english, 2002
11

P-selectivity: Intersections and indices

Year:
1995
Language:
english
File:
PDF, 645 KB
english, 1995
12

Quasi-injective reductions

Year:
1994
Language:
english
File:
PDF, 436 KB
english, 1994
13

Optimal advice

Year:
1996
Language:
english
File:
PDF, 788 KB
english, 1996
14

Reductibility classes of P-selective sets

Year:
1996
Language:
english
File:
PDF, 807 KB
english, 1996
15

The consequences of eliminating NP solutions

Year:
2008
Language:
english
File:
PDF, 575 KB
english, 2008
18

Dichotomy for voting systems

Year:
2007
Language:
english
File:
PDF, 162 KB
english, 2007
19

If then some strongly noninvertible functions are invertible

Year:
2006
Language:
english
File:
PDF, 199 KB
english, 2006
20

Query-monotonic Turing reductions

Year:
2007
Language:
english
File:
PDF, 779 KB
english, 2007
22

The complexity of power-index comparison

Year:
2009
Language:
english
File:
PDF, 505 KB
english, 2009
23

Generalized juntas and NP-hard sets

Year:
2009
Language:
english
File:
PDF, 406 KB
english, 2009
24

On the complexity of kings

Year:
2010
Language:
english
File:
PDF, 1.15 MB
english, 2010
25

On characterizing the existence of partial one-way permutations

Year:
2002
Language:
english
File:
PDF, 84 KB
english, 2002
26

Characterizing the existence of one-way permutations

Year:
2000
Language:
english
File:
PDF, 69 KB
english, 2000
27

P-immune sets with holes lack self-reducibility properties

Year:
2003
Language:
english
File:
PDF, 221 KB
english, 2003
29

A second step towards complexity-theoretic analogs of Rice's Theorem

Year:
2000
Language:
english
File:
PDF, 122 KB
english, 2000
30

Space-efficient recognition of sparse self-reducible languages

Year:
1994
Language:
english
File:
PDF, 2.28 MB
english, 1994
32

Easy sets and hard certificate schemes

Year:
1997
Language:
english
File:
PDF, 253 KB
english, 1997
34

Lower bounds and the hardness of counting properties

Year:
2004
Language:
english
File:
PDF, 377 KB
english, 2004
35

All superlinear inverse schemes are coNP-hard

Year:
2005
Language:
english
File:
PDF, 156 KB
english, 2005
36

Almost-Everywhere Superiority for Quantum Polynomial Time

Year:
2002
Language:
english
File:
PDF, 113 KB
english, 2002
40

Cluster computing and the power of edge recognition

Year:
2007
Language:
english
File:
PDF, 622 KB
english, 2007
43

Easily Checked Generalized Self-Reducibility

Year:
1995
Language:
english
File:
PDF, 2.60 MB
english, 1995
44

Threshold Computation and Cryptographic Security

Year:
1997
Language:
english
File:
PDF, 403 KB
english, 1997
45

A Downward Collapse within the Polynomial Hierarchy

Year:
1998
Language:
english
File:
PDF, 336 KB
english, 1998
46

Query Order

Year:
1998
Language:
english
File:
PDF, 376 KB
english, 1998
47

Unambiguous Computation: Boolean Hierarchies and Sparse Turing-Complete Sets

Year:
1997
Language:
english
File:
PDF, 420 KB
english, 1997
49

Algebraic Properties for Selector Functions

Year:
2004
Language:
english
File:
PDF, 296 KB
english, 2004